import org.w3c.dom.*;

import java.util.*;
import java.util.function.BiConsumer;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 刘远望
 * Date: 2025-04-30
 * Time: 22:13
 */
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
    }
}
public class Test {

    //返回前k个单词出现频率最高的单词，出现频率由高到低，若相同则按字典顺序排行
    public static List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> hashMap = new HashMap<>();
        //1.计算每个单词出现的次数
        for (String s : words) {
            if (hashMap.get(s) == null) {
                hashMap.put(s, 1);
            } else {
                int val = hashMap.get(s);
                hashMap.put(s, val + 1);
            }
        }

        //2.建立小根堆
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        //3.遍历Map(入堆)
        for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                Map.Entry<String, Integer> top = minHeap.peek();
                if (top.getValue().compareTo(entry.getValue()) < 0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                } else if (top.getValue().compareTo(entry.getValue()) == 0) {
                    if (top.getKey().compareTo(entry.getKey()) > 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        ArrayList<String> arrayList = new ArrayList<>();

        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> tmp = minHeap.poll();
            arrayList.add(tmp.getKey());
        }

        //反转数组
        Collections.reverse(arrayList);
        return arrayList;
    }
    public static void main(String[] args) {
        String[] words = {"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"};
        List<String> ret = topKFrequent(words, 4);
        for (String s : ret) {
            System.out.println(s);
        }
    }

    //坏键盘打字(统一大写)
    public static void func(String str1, String str2) {
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();

        HashSet<Character> hashAct = new HashSet<>();
        for (int i = 0; i < str2.length(); i++) {
            char ch = str2.charAt(i);
            hashAct.add(ch);
        }

        HashSet<Character> hashBorken = new HashSet<>();
        for (int i = 0; i < str1.length(); i++) {
            char ch = str1.charAt(i);
            if(!hashAct.contains(ch) && !hashBorken.contains(ch)) {
                hashBorken.add(ch);
                System.out.print(ch);
            }
        }
    }
    public static void main4(String[] args) {
        func("7_This_is_a_test", "_hs_s_a_es");
    }

    //给定一个字符串， 看另外一个字符串有多少 前面字符串的字符， 区分大小写
    public static int numJewelsStones(String jewels, String stones) {
        HashSet<Character> hashSet = new HashSet<>();
        for (int i = 0; i < jewels.length(); i++) {
            char ch = jewels.charAt(i);
            hashSet.add(ch);
        }
        int count = 0;
        for (int i = 0; i < stones.length(); i++) {
            char ch = stones.charAt(i);
            if(hashSet.contains(ch)) {
                count++;
            }
        }
        return count;
    }
    public static void main3(String[] args) {
        String jewels = "aA";
        String stones = "aaaABBBBBAAaaccjj";
        int ret = numJewelsStones(jewels, stones);
        System.out.println(ret);
    }

    //链表的深层拷贝
    public Node copyRandomList(Node head) {
        //一个Node是老节点，一个是新节点
        HashMap<Node, Node> hashMap = new HashMap<>();
        Node cur = head;
        //第一次遍历不知道下一个节点是谁，就要先创建新节点
        while (cur != null) {
            Node node = new Node(cur.val);
            hashMap.put(cur, node);//老节点cur 新节点node
            cur = cur.next;
        }
        cur = head;
        //新节点前后对应
        while (cur != null) {
            hashMap.get(cur).next = hashMap.get(cur.next);
            hashMap.get(cur).random = hashMap.get(cur.random);
            cur = cur.next;
        }

        return hashMap.get(head);
    }

    //只出现一次的元素
    public static int singleNumber(int[] arr) {
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < arr.length; i++) {
            if(!set.contains(arr[i])) {
                set.add(arr[i]);
            }else {
                set.remove(arr[i]);
            }
        }

        for (int i = 0; i < arr.length; i++) {
            if(set.contains(arr[i])) {
                return arr[i];
            }
        }
        return -1;
    }
    public static void main2(String[] args) {
        int[] arr = {1, 2, 2, 3, 3, 1, 5, 6, 7, 5, 6, 9, 7};
        int ret = singleNumber(arr);
        System.out.println(ret);
    }

    //计数单词出现的次数
    public static Map<String, Integer> countWord(String[] words) {
        Map<String, Integer> map = new HashMap<>();
        for (String s : words) {
            if (map.get(s) == null) {
                map.put(s, 1);
            }else {
                int val = map.get(s);
                map.put(s, val + 1);
            }
        }
        return map;
    }
    public static void main1(String[] args) {
        String[] words = {"hello", "hello" , "word", "word", "this", "hello", "this", "bit"};
        Map<String, Integer> map = countWord(words);
        //法1匿名内部类
       /* map.forEach(new BiConsumer<String, Integer>() {
            @Override
            public void accept(String s, Integer integer) {
                System.out.println("key: " + s + " val: " + integer);
            }
        });*/

        //法2 lambad表达式
        //map.forEach((key,val) -> System.out.println("key: " + key + " val: " + val));

        //法3 set结合
        Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
        for (Map.Entry<String, Integer> entry : entrySet) {
            System.out.println("key: " + entry.getKey() + " val: " + entry.getValue());
        }
    }
}
